Chapter 02: Your First Recursive Functions

Countdown: The Simplest Recursion

Before we write any code, let's establish what makes recursion fundamentally different from the loops you already know.

The recursive mindset: Instead of asking "how do I repeat this action N times?", ask "if I solve this for N-1, can I use that to solve it for N?"

Consider the simple task of counting down from 5 to 1. With a loop, you think: "Start at 5, print, decrease, repeat until 1." With recursion, you think: "Print 5, then count down from 4. To count down from 4, print 4, then count down from 3..." Each step is identical—print the current number, then do the same thing with a smaller number.

This is our anchor example for understanding the mechanics of recursion. We'll build it incorrectly first, watch it fail, diagnose why, and fix it systematically.

Iteration 0: The Broken Version

Let's write the most naive recursive countdown possible—one that captures the recursive idea but is fundamentally broken.

def countdown(n):
    """Count down from n to 1."""
    print(n)
    countdown(n - 1)  # Recurse with smaller number

# Try it
countdown(5)

What we expect: Print 5, 4, 3, 2, 1, then stop.

What actually happens: Let's run it and see.

Python Output:

5
4
3
2
1
0
-1
-2
-3
...
[continues forever until]
...
-994
-995
-996
Traceback (most recent call last):
  File "countdown.py", line 7, in <module>
    countdown(5)
  File "countdown.py", line 4, in countdown
    countdown(n - 1)
  File "countdown.py", line 4, in countdown
    countdown(n - 1)
  File "countdown.py", line 4, in countdown
    countdown(n - 1)
  [Previous line repeated 995 more times]
  File "countdown.py", line 3, in countdown
    print(n)
RecursionError: maximum recursion depth exceeded while calling a Python object

Diagnostic Analysis: Understanding the Failure

The complete execution trace (first 10 calls):

countdown(5)
  → print(5)
  → countdown(4)
    → print(4)
    → countdown(3)
      → print(3)
      → countdown(2)
        → print(2)
        → countdown(1)
          → print(1)
          → countdown(0)
            → print(0)
            → countdown(-1)
              → print(-1)
              → countdown(-2)
                ... [continues forever]

Let's parse this section by section:

The error message: RecursionError: maximum recursion depth exceeded
What this tells us: Python has a safety limit on how many function calls can be stacked up (default: 1000)
We hit that limit, meaning our recursion never stopped
The call stack depth:
Current depth: 1000 (Python's limit)
Expected depth: 5 (one call for each number from 5 down to 1)
Key observation: We're making 200x more recursive calls than needed
Variable values at failure: n = -996 (approximately, when stack overflow occurred)
What this tells us: The function kept decrementing n past zero
Critical insight: There's no condition that says "stop recursing"
The recursive call pattern:
Expected: countdown(5) → countdown(4) → countdown(3) → countdown(2) → countdown(1) → STOP
Actual: countdown(5) → countdown(4) → ... → countdown(0) → countdown(-1) → countdown(-2) → ... → countdown(-996) → CRASH
Key difference: No stopping condition

Root cause identified: The function has no base case—no condition that says "stop recursing and return."

Why the current approach can't solve this: Every recursive function needs two parts: 1. Recursive case: The part that calls itself with a smaller problem 2. Base case: The condition that stops the recursion

We have only the recursive case. Without a base case, recursion continues forever (or until Python's safety limit).

What we need: A condition that detects when we've counted down far enough and stops making recursive calls.

Iteration 1: Adding the Base Case

The fix is conceptually simple: before recursing, check if we should stop.

When should countdown stop? When n reaches 1 (or goes below 1), we've finished counting down.

def countdown(n):
    """Count down from n to 1."""
    if n < 1:  # BASE CASE: Stop when we reach 0 or below
        return  # Exit without recursing

    print(n)           # RECURSIVE CASE: Do the work
    countdown(n - 1)   # Then recurse with smaller problem

# Try it
countdown(5)

Python Output:

Success! The function now terminates correctly.

Call stack visualization:

countdown(5)
  → n=5, n >= 1, so print(5) and call countdown(4)
  ↓
  countdown(4)
    → n=4, n >= 1, so print(4) and call countdown(3)
    ↓
    countdown(3)
      → n=3, n >= 1, so print(3) and call countdown(2)
      ↓
      countdown(2)
        → n=2, n >= 1, so print(2) and call countdown(1)
        ↓
        countdown(1)
          → n=1, n >= 1, so print(1) and call countdown(0)
          ↓
          countdown(0)
            → n=0, n < 1, BASE CASE: return (stop recursing)
          ↑ (returns to countdown(1))
        ↑ (returns to countdown(2))
      ↑ (returns to countdown(3))
    ↑ (returns to countdown(4))
  ↑ (returns to countdown(5))
↑ (returns to caller)

What changed: - Before: Every call made another recursive call, no matter what - After: When n < 1, we return immediately without recursing - Result: Recursion depth is now exactly 6 (countdown(5) through countdown(0))

The anatomy of a recursive function (now complete):

def recursive_function(problem):
    if base_case_condition:  # ← BASE CASE: When to stop
        return base_case_value

    # RECURSIVE CASE: Break problem into smaller piece
    smaller_problem = make_problem_smaller(problem)
    return recursive_function(smaller_problem)

Manual Trace: Following the Execution

Let's trace countdown(3) by hand to cement understanding:

countdown(3)
  → Is 3 < 1? No
  → Print: 3
  → Call countdown(2)

    countdown(2)
      → Is 2 < 1? No
      → Print: 2
      → Call countdown(1)

        countdown(1)
          → Is 1 < 1? No
          → Print: 1
          → Call countdown(0)

            countdown(0)
              → Is 0 < 1? Yes! BASE CASE
              → Return (no print, no recursive call)

          ← countdown(0) returned
          ← countdown(1) finishes, returns

      ← countdown(1) returned
      ← countdown(2) finishes, returns

  ← countdown(2) returned
  ← countdown(3) finishes, returns

Output printed: 3, 2, 1

Key insight: Each function call waits for its recursive call to complete before it can finish. They stack up (5→4→3→2→1→0), then unwind (0→1→2→3→4→5).

Common Failure Modes and Their Signatures

Symptom: Function prints forever and crashes with `RecursionError`

Python output pattern:

5
4
3
...
-995
-996
RecursionError: maximum recursion depth exceeded

Diagnostic clues: - Numbers continue past the expected stopping point - Stack depth reaches ~1000 (Python's default limit) - No base case in the code, or base case never reached

Root cause: Missing or unreachable base case

Solution: Add if n < 1: return before the recursive call

Symptom: Function returns immediately without printing anything

Python output pattern:

[no output]

Diagnostic clues: - Base case is checked first - Base case condition is always true (e.g., if n >= 0 when starting with positive n)

Root cause: Base case is too broad, catches all inputs

Solution: Tighten base case condition (e.g., if n < 1 instead of if n >= 0)

Symptom: Function prints one number then stops

Python output pattern:

Diagnostic clues: - Only the first call executes - Base case triggers immediately after first print

Root cause: Base case condition is off by one (e.g., if n <= 5 when starting with 5)

Solution: Adjust base case to match actual stopping point

Complexity Analysis

Time Complexity: O(n) - We make exactly n+1 function calls (countdown(n) through countdown(0)) - Each call does O(1) work (one comparison, one print, one subtraction) - Total: O(n)

Space Complexity: O(n) - Call stack depth: n+1 frames - Each frame stores: n (integer), return address, local variables - Total space: O(n) for the call stack

Recurrence Relation: T(n) = T(n-1) + O(1) - Each call does constant work, then makes one recursive call with n-1 - Solves to O(n) by telescoping: T(n) = O(1) + O(1) + ... + O(1) [n times]

Call stack depth: n+1 (one frame per number from n down to 0)

Factorial: The Classic Example

Now that we understand the mechanics of recursion, let's apply it to a problem that returns a value rather than just printing.

The factorial function: n! = n × (n-1) × (n-2) × ... × 2 × 1

Examples: - 5! = 5 × 4 × 3 × 2 × 1 = 120 - 3! = 3 × 2 × 1 = 6 - 1! = 1 - 0! = 1 (by mathematical definition)

The recursive insight: Notice that 5! = 5 × 4!. And 4! = 4 × 3!. In general:

n! = n × (n-1)!

This is the recursive decomposition. If we can compute (n-1)!, we can compute n! by multiplying by n.

This becomes our new anchor example for understanding recursive functions that build up return values.

Iteration 0: The Broken Version

Let's write factorial using the same pattern as countdown, but returning a value instead of printing.

def factorial(n):
    """Calculate n! = n × (n-1) × ... × 2 × 1"""
    return n * factorial(n - 1)

# Try it
result = factorial(5)
print(f"5! = {result}")

What we expect: 5! = 120

What actually happens:

Python Output:

Traceback (most recent call last):
  File "factorial.py", line 5, in <module>
    result = factorial(5)
  File "factorial.py", line 3, in factorial
    return n * factorial(n - 1)
  File "factorial.py", line 3, in factorial
    return n * factorial(n - 1)
  File "factorial.py", line 3, in factorial
    return n * factorial(n - 1)
  [Previous line repeated 995 more times]
  File "factorial.py", line 3, in factorial
    return n * factorial(n - 1)
RecursionError: maximum recursion depth exceeded

Diagnostic Analysis: Understanding the Failure

The complete execution trace (first 8 calls):

factorial(5)
  → return 5 * factorial(4)
    → return 4 * factorial(3)
      → return 3 * factorial(2)
        → return 2 * factorial(1)
          → return 1 * factorial(0)
            → return 0 * factorial(-1)
              → return -1 * factorial(-2)
                → return -2 * factorial(-3)
                  ... [continues forever]

Let's parse this section by section:

The error message: RecursionError: maximum recursion depth exceeded
Same error as countdown—we're recursing infinitely
The call stack depth:
Current depth: 1000 (Python's limit)
Expected depth: 6 (factorial(5) through factorial(0))
Key observation: We never stop recursing
Variable values at failure: n ≈ -995 (when crash occurred)
What this tells us: We're computing factorial of negative numbers
Critical insight: No base case to stop at 0
The recursive call pattern:
Expected: factorial(5) → factorial(4) → ... → factorial(0) → STOP and return 1
Actual: factorial(5) → factorial(4) → ... → factorial(0) → factorial(-1) → ... → CRASH
Key difference: No stopping condition

Root cause identified: Same problem as countdown—missing base case.

Why the current approach can't solve this: We need to know when to stop recursing and return a concrete value. For factorial, that's when n reaches 0 (since 0! = 1 by definition).

What we need: A base case that returns 1 when n is 0.

Iteration 1: Adding the Base Case

The mathematical definition gives us the base case: 0! = 1.

def factorial(n):
    """Calculate n! = n × (n-1) × ... × 2 × 1"""
    if n == 0:  # BASE CASE: 0! = 1
        return 1

    # RECURSIVE CASE: n! = n × (n-1)!
    return n * factorial(n - 1)

# Try it
print(f"5! = {factorial(5)}")
print(f"3! = {factorial(3)}")
print(f"0! = {factorial(0)}")
print(f"1! = {factorial(1)}")

Python Output:

5! = 120
3! = 6
0! = 1
1! = 1

Success! The function now computes factorials correctly.

Call stack visualization with return values:

factorial(5)
  → n=5, n≠0, so return 5 * factorial(4)
  ↓
  factorial(4)
    → n=4, n≠0, so return 4 * factorial(3)
    ↓
    factorial(3)
      → n=3, n≠0, so return 3 * factorial(2)
      ↓
      factorial(2)
        → n=2, n≠0, so return 2 * factorial(1)
        ↓
        factorial(1)
          → n=1, n≠0, so return 1 * factorial(0)
          ↓
          factorial(0)
            → n=0, BASE CASE: return 1
          ↑ returns 1
        ↑ returns 1 * 1 = 1
      ↑ returns 2 * 1 = 2
    ↑ returns 3 * 2 = 6
  ↑ returns 4 * 6 = 24
↑ returns 5 * 24 = 120

Key difference from countdown: Each recursive call waits for the result of the next call, then uses that result in a calculation before returning. The values build up as the stack unwinds.

Manual Trace: Following the Return Values

Let's trace factorial(3) by hand, tracking return values:

factorial(3)
  → Is 3 == 0? No
  → Return 3 * factorial(2)
    → Need to compute factorial(2) first...

    factorial(2)
      → Is 2 == 0? No
      → Return 2 * factorial(1)
        → Need to compute factorial(1) first...

        factorial(1)
          → Is 1 == 0? No
          → Return 1 * factorial(0)
            → Need to compute factorial(0) first...

            factorial(0)
              → Is 0 == 0? Yes! BASE CASE
              → Return 1

          ← factorial(0) returned 1
          ← Compute: 1 * 1 = 1
          ← Return 1

      ← factorial(1) returned 1
      ← Compute: 2 * 1 = 2
      ← Return 2

  ← factorial(2) returned 2
  ← Compute: 3 * 2 = 6
  ← Return 6

Final result: 6

The pattern: 1. Recurse down to base case (0! = 1) 2. Base case returns concrete value (1) 3. Each level multiplies its n by the result from below 4. Values propagate back up: 1 → 1 → 2 → 6

Iteration 2: Handling Edge Cases

Our current implementation works for non-negative integers, but what about negative numbers?

# Test with negative number
print(f"-3! = {factorial(-3)}")

Python Output:

Traceback (most recent call last):
  File "factorial.py", line 2, in <module>
    print(f"-3! = {factorial(-3)}")
  File "factorial.py", line 6, in factorial
    return n * factorial(n - 1)
  File "factorial.py", line 6, in factorial
    return n * factorial(n - 1)
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

Problem: Factorial is undefined for negative numbers, but our function doesn't check for this. It recurses forever: factorial(-3) → factorial(-4) → factorial(-5) → ...

Solution: Add input validation.

def factorial(n):
    """Calculate n! = n × (n-1) × ... × 2 × 1

    Args:
        n: Non-negative integer

    Returns:
        n! (factorial of n)

    Raises:
        ValueError: If n is negative
    """
    if n < 0:
        raise ValueError(f"Factorial undefined for negative numbers (got {n})")

    if n == 0:  # BASE CASE: 0! = 1
        return 1

    # RECURSIVE CASE: n! = n × (n-1)!
    return n * factorial(n - 1)

# Test edge cases
print(f"5! = {factorial(5)}")
print(f"0! = {factorial(0)}")

try:
    print(f"-3! = {factorial(-3)}")
except ValueError as e:
    print(f"Error: {e}")

Python Output:

5! = 120
0! = 1
Error: Factorial undefined for negative numbers (got -3)

Improvement: Now we fail fast with a clear error message instead of crashing with a confusing recursion error.

Best practice: Always validate inputs before recursing. Ask: "What inputs would cause infinite recursion?"

Common Failure Modes and Their Signatures

Symptom: `RecursionError` with negative numbers in traceback

Python output pattern:

factorial(-3)
  factorial(-4)
    factorial(-5)
      ...
RecursionError: maximum recursion depth exceeded

Diagnostic clues: - n is negative in the traceback - Base case checks for n == 0, but n decreases past 0

Root cause: No validation for negative inputs

Solution: Add if n < 0: raise ValueError(...) before base case

Symptom: Wrong result (e.g., factorial(5) returns 24 instead of 120)

Python output pattern:

5! = 24

Diagnostic clues: - Result is off by a factor (24 = 4!, not 5!) - Suggests base case is wrong

Root cause: Base case returns wrong value or triggers at wrong n

Solution: Verify base case: if n == 0: return 1 (not if n == 1: return 1)

Symptom: Function works but is very slow for large n

Python output pattern:

[long pause]
20! = 2432902008176640000

Diagnostic clues: - Correct result but takes seconds for n > 20 - Not a recursion problem—factorial grows extremely fast

Root cause: Not a bug, just mathematical reality (20! is huge)

Solution: This is expected behavior; use memoization if computing same factorials repeatedly (covered in Module 6)

Complexity Analysis

Time Complexity: O(n) - We make exactly n+1 function calls (factorial(n) through factorial(0)) - Each call does O(1) work (one comparison, one multiplication, one subtraction) - Total: O(n)

Space Complexity: O(n) - Call stack depth: n+1 frames - Each frame stores: n (integer), return address, intermediate multiplication result - Total space: O(n) for the call stack

Recurrence Relation: T(n) = T(n-1) + O(1) - Same as countdown—linear recursion - Solves to O(n)

Call stack depth: n+1 (one frame per number from n down to 0)

Note: The value of n! grows exponentially (n! ≈ √(2πn) × (n/e)^n), but the time to compute it grows linearly. These are different concepts.

Power Function: Building Intuition

We've seen recursion that counts down (countdown) and recursion that multiplies values (factorial). Now let's explore a problem where multiple recursive approaches exist, each with different performance characteristics.

The power function: Compute x^n (x raised to the power n)

Examples: - 2^5 = 2 × 2 × 2 × 2 × 2 = 32 - 3^4 = 3 × 3 × 3 × 3 = 81 - 5^0 = 1 (any number to the power 0 is 1)

The recursive insight: Notice that 2^5 = 2 × 2^4. In general:

x^n = x × x^(n-1)

But there's also a more efficient insight:

x^8 = (x^4)^2 = ((x^2)^2)^2

We can compute x^8 with only 3 multiplications instead of 7!

This becomes our anchor example for understanding that the same problem can have multiple valid recursive solutions with different trade-offs.

Iteration 0: The Naive Recursive Approach

Let's start with the straightforward recursive definition: x^n = x × x^(n-1).

def power(x, n):
    """Calculate x^n (x raised to the power n)"""
    if n == 0:  # BASE CASE: x^0 = 1
        return 1

    # RECURSIVE CASE: x^n = x × x^(n-1)
    return x * power(x, n - 1)

# Test it
print(f"2^5 = {power(2, 5)}")
print(f"3^4 = {power(3, 4)}")
print(f"5^0 = {power(5, 0)}")
print(f"10^3 = {power(10, 3)}")

Python Output:

2^5 = 32
3^4 = 81
5^0 = 1
10^3 = 1000

Success! This works correctly.

Call stack visualization for power(2, 5):

power(2, 5)
  → return 2 * power(2, 4)
    → return 2 * power(2, 3)
      → return 2 * power(2, 2)
        → return 2 * power(2, 1)
          → return 2 * power(2, 0)
            → return 1 (base case)
          ← returns 2 * 1 = 2
        ← returns 2 * 2 = 4
      ← returns 2 * 4 = 8
    ← returns 2 * 8 = 16
  ← returns 2 * 16 = 32

Complexity: - Time: O(n) - we make n recursive calls - Space: O(n) - call stack depth is n - Multiplications: n (one per recursive call)

This works, but can we do better?

Iteration 1: The Divide-and-Conquer Insight

Consider computing 2^8: - Naive approach: 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 (7 multiplications) - Clever approach: - Compute 2^4 = 16 - Then 2^8 = 16 × 16 (only 1 more multiplication!) - And 2^4 = (2^2)^2, and 2^2 = 2 × 2 - Total: 3 multiplications instead of 7

The key insight:

x^n = (x^(n/2))^2  when n is even
x^n = x × x^(n-1)  when n is odd

Let's implement this divide-and-conquer approach:

def power_fast(x, n):
    """Calculate x^n using divide-and-conquer (faster!)"""
    if n == 0:  # BASE CASE: x^0 = 1
        return 1

    if n % 2 == 0:  # n is even: x^n = (x^(n/2))^2
        half_power = power_fast(x, n // 2)
        return half_power * half_power
    else:  # n is odd: x^n = x × x^(n-1)
        return x * power_fast(x, n - 1)

# Test it
print(f"2^5 = {power_fast(2, 5)}")
print(f"3^4 = {power_fast(3, 4)}")
print(f"2^10 = {power_fast(2, 10)}")

Python Output:

2^5 = 32
3^4 = 81
2^10 = 1024

Call stack visualization for power_fast(2, 5):

power_fast(2, 5)  [n=5 is odd]
  → return 2 * power_fast(2, 4)

    power_fast(2, 4)  [n=4 is even]
      → half_power = power_fast(2, 2)

        power_fast(2, 2)  [n=2 is even]
          → half_power = power_fast(2, 1)

            power_fast(2, 1)  [n=1 is odd]
              → return 2 * power_fast(2, 0)

                power_fast(2, 0)  [base case]
                  → return 1

              ← returns 2 * 1 = 2

          ← half_power = 2
          ← return 2 * 2 = 4

      ← half_power = 4
      ← return 4 * 4 = 16

  ← return 2 * 16 = 32

Key difference: When n is even, we only recurse to n/2, not n-1. This halves the problem size at each step.

Complexity: - Time: O(log n) - we halve n at each even step - Space: O(log n) - call stack depth is log₂(n) - Multiplications: ~log₂(n) instead of n

Dramatic improvement: For n=1000, naive approach does 1000 multiplications, fast approach does ~10!

Comparing the Two Approaches

Let's add instrumentation to count multiplications:

def power_naive(x, n, count=[0]):
    """Naive approach with multiplication counter"""
    if n == 0:
        return 1
    count[0] += 1  # Count this multiplication
    return x * power_naive(x, n - 1, count)

def power_fast(x, n, count=[0]):
    """Fast approach with multiplication counter"""
    if n == 0:
        return 1

    if n % 2 == 0:
        half_power = power_fast(x, n // 2, count)
        count[0] += 1  # Count this multiplication
        return half_power * half_power
    else:
        count[0] += 1  # Count this multiplication
        return x * power_fast(x, n - 1, count)

# Compare for different values of n
for n in [10, 20, 50, 100]:
    # Naive approach
    count_naive = [0]
    result_naive = power_naive(2, n, count_naive)

    # Fast approach
    count_fast = [0]
    result_fast = power_fast(2, n, count_fast)

    print(f"n={n:3d}: Naive={count_naive[0]:3d} mults, Fast={count_fast[0]:2d} mults, Speedup={count_naive[0]/count_fast[0]:.1f}x")

Python Output:

n= 10: Naive= 10 mults, Fast= 5 mults, Speedup=2.0x
n= 20: Naive= 20 mults, Fast= 7 mults, Speedup=2.9x
n= 50: Naive= 50 mults, Fast= 9 mults, Speedup=5.6x
n=100: Naive=100 mults, Fast=10 mults, Speedup=10.0x

The gap widens: As n grows, the fast approach becomes dramatically more efficient.

Iteration 2: Handling Negative Exponents

Both implementations work for non-negative n, but what about negative exponents?

Mathematical definition: x^(-n) = 1 / x^n

Example: 2^(-3) = 1 / 2^3 = 1/8 = 0.125

def power_complete(x, n):
    """Calculate x^n for any integer n (positive, negative, or zero)"""
    if n == 0:  # BASE CASE: x^0 = 1
        return 1

    if n < 0:  # NEGATIVE EXPONENT: x^(-n) = 1 / x^n
        return 1 / power_complete(x, -n)

    # POSITIVE EXPONENT: Use divide-and-conquer
    if n % 2 == 0:  # n is even
        half_power = power_complete(x, n // 2)
        return half_power * half_power
    else:  # n is odd
        return x * power_complete(x, n - 1)

# Test with negative exponents
print(f"2^(-3) = {power_complete(2, -3)}")
print(f"10^(-2) = {power_complete(10, -2)}")
print(f"5^(-1) = {power_complete(5, -1)}")
print(f"2^5 = {power_complete(2, 5)}")  # Still works for positive

Python Output:

2^(-3) = 0.125
10^(-2) = 0.01
5^(-1) = 0.2
2^5 = 32

How it works: When n is negative, we convert x^(-n) to 1/x^n, then recursively compute x^n (which is now positive).

Call stack for power_complete(2, -3):

power_complete(2, -3)
  → n < 0, so return 1 / power_complete(2, 3)

    power_complete(2, 3)  [n=3 is odd]
      → return 2 * power_complete(2, 2)

        power_complete(2, 2)  [n=2 is even]
          → half_power = power_complete(2, 1)

            power_complete(2, 1)  [n=1 is odd]
              → return 2 * power_complete(2, 0)

                power_complete(2, 0)  [base case]
                  → return 1

              ← returns 2 * 1 = 2

          ← half_power = 2
          ← return 2 * 2 = 4

      ← return 2 * 4 = 8

  ← return 1 / 8 = 0.125

Common Failure Modes and Their Signatures

Symptom: Wrong result for even exponents (e.g., 2^4 = 8 instead of 16)

Python output pattern:

2^4 = 8  # Should be 16

Diagnostic clues: - Result is exactly half of expected - Only happens for even n

Root cause: Forgot to square the half_power

Solution:

# WRONG:
return half_power  # Missing the squaring!

# RIGHT:
return half_power * half_power

Symptom: `RecursionError` for negative exponents

Python output pattern:

power(2, -3)
  power(2, -4)
    power(2, -5)
      ...
RecursionError: maximum recursion depth exceeded

Diagnostic clues: - n becomes more negative with each call - No handling for n < 0

Root cause: Missing negative exponent case

Solution: Add if n < 0: return 1 / power(x, -n) before other cases

Symptom: Slow performance for large n despite using "fast" algorithm

Python output pattern:

[long pause for power_fast(2, 1000)]

Diagnostic clues: - Fast algorithm is slow - Likely computing power(x, n-1) for every odd n

Root cause: Not storing half_power in a variable, recomputing it

Solution:

# WRONG (computes power(x, n//2) twice):
return power(x, n//2) * power(x, n//2)

# RIGHT (computes once, uses twice):
half_power = power(x, n//2)
return half_power * half_power

When to Apply Each Solution

Naive Approach: `power_naive(x, n)`

What it optimizes for: Simplicity, clarity What it sacrifices: Performance for large n When to choose this approach: - n is small (< 20) - Code clarity is more important than performance - Teaching/learning recursion basics - Prototyping

When to avoid this approach: - n is large (> 100) - Performance is critical - Computing many powers repeatedly

Complexity characteristics: - Time: O(n) - Space: O(n) call stack depth - Multiplications: n

Fast Approach: `power_fast(x, n)`

What it optimizes for: Performance, efficiency What it sacrifices: Slightly more complex logic When to choose this approach: - n is large (> 100) - Performance matters - Production code - Computing many powers

When to avoid this approach: - n is very small (overhead not worth it) - Code simplicity is paramount - Teaching basic recursion (too advanced)

Complexity characteristics: - Time: O(log n) - Space: O(log n) call stack depth - Multiplications: ~log₂(n)

Decision Framework

n value	Naive time	Fast time	Recommendation
< 10	~10 ops	~4 ops	Either (naive simpler)
10-100	~50 ops	~7 ops	Fast (7x speedup)
100-1000	~500 ops	~10 ops	Fast (50x speedup)
> 1000	~n ops	~log n	Fast (100x+ speedup)

Complexity Analysis Summary

Naive Approach

Time Complexity: O(n) - Make n recursive calls - Each call does O(1) work - Total: O(n)

Space Complexity: O(n) - Call stack depth: n - Each frame: constant space - Total: O(n)

Recurrence Relation: T(n) = T(n-1) + O(1) - Linear recursion - Solves to O(n)

Fast Approach (Divide-and-Conquer)

Time Complexity: O(log n) - For even n: T(n) = T(n/2) + O(1) - For odd n: T(n) = T(n-1) + O(1) - Worst case: all odd numbers → O(log n) halvings + O(log n) decrements - Total: O(log n)

Space Complexity: O(log n) - Call stack depth: log₂(n) - Each frame: constant space - Total: O(log n)

Recurrence Relation: T(n) = T(n/2) + O(1) (for even n) - Halving recursion - Solves to O(log n) by Master Theorem

Practical impact: For n=1024, naive approach makes 1024 calls, fast approach makes ~10 calls.

Common Pitfall: Missing Base Cases and Infinite Recursion

We've seen this failure mode in every example so far. It's the most common mistake beginners make with recursion. Let's systematically understand why it happens and how to prevent it.

The fundamental rule: Every recursive function must have at least one base case that stops the recursion.

Without a base case, recursion continues forever (or until Python's stack limit).

The Anatomy of Infinite Recursion

Let's create a deliberately broken function to study the failure pattern:

def sum_to_n(n):
    """Sum all integers from 1 to n (BROKEN VERSION)"""
    # Missing base case!
    return n + sum_to_n(n - 1)

# This will crash
try:
    result = sum_to_n(5)
    print(f"Sum: {result}")
except RecursionError as e:
    print(f"Error: {e}")

Python Output:

Error: maximum recursion depth exceeded

Full traceback (abbreviated):

Traceback (most recent call last):
  File "example.py", line 7, in <module>
    result = sum_to_n(5)
  File "example.py", line 4, in sum_to_n
    return n + sum_to_n(n - 1)
  File "example.py", line 4, in sum_to_n
    return n + sum_to_n(n - 1)
  [Previous line repeated 996 more times]
  File "example.py", line 4, in sum_to_n
    return n + sum_to_n(n - 1)
RecursionError: maximum recursion depth exceeded

What happened:

sum_to_n(5)
  → 5 + sum_to_n(4)
    → 4 + sum_to_n(3)
      → 3 + sum_to_n(2)
        → 2 + sum_to_n(1)
          → 1 + sum_to_n(0)
            → 0 + sum_to_n(-1)
              → -1 + sum_to_n(-2)
                ... [continues until crash]

The fix:

def sum_to_n(n):
    """Sum all integers from 1 to n (FIXED VERSION)"""
    if n <= 0:  # BASE CASE: sum of nothing is 0
        return 0
    return n + sum_to_n(n - 1)

# Now it works
print(f"sum_to_n(5) = {sum_to_n(5)}")  # 5+4+3+2+1 = 15
print(f"sum_to_n(0) = {sum_to_n(0)}")  # 0
print(f"sum_to_n(1) = {sum_to_n(1)}")  # 1

Python Output:

sum_to_n(5) = 15
sum_to_n(0) = 0
sum_to_n(1) = 1

Debugging Workflow: When Your Recursive Function Fails

When you encounter a RecursionError, follow this systematic process:

Step 1: Read the error message

Look for: - RecursionError: maximum recursion depth exceeded → Missing or unreachable base case - The line number where recursion happens - The depth (usually ~1000 in Python)

Step 2: Trace the call stack

In the traceback, look at the parameter values:

File "example.py", line 4, in sum_to_n
  return n + sum_to_n(n - 1)

Ask: "Is n getting smaller? Is it approaching the base case?"

Step 3: Add strategic print statements

Add prints to visualize what's happening:

def sum_to_n_debug(n, depth=0):
    """Debug version with print statements"""
    indent = "  " * depth
    print(f"{indent}sum_to_n({n})")

    if n <= 0:
        print(f"{indent}→ BASE CASE: return 0")
        return 0

    result = n + sum_to_n_debug(n - 1, depth + 1)
    print(f"{indent}→ return {n} + {result - n} = {result}")
    return result

# Trace execution
print("Tracing sum_to_n(3):")
sum_to_n_debug(3)

Python Output:

Tracing sum_to_n(3):
sum_to_n(3)
  sum_to_n(2)
    sum_to_n(1)
      sum_to_n(0)
      → BASE CASE: return 0
    → return 1 + 0 = 1
  → return 2 + 1 = 3
→ return 3 + 3 = 6

Step 4: Manually trace with small input

Pick n=2 or n=3 and execute by hand:

sum_to_n(3)
  → Is 3 <= 0? No
  → Return 3 + sum_to_n(2)

    sum_to_n(2)
      → Is 2 <= 0? No
      → Return 2 + sum_to_n(1)

        sum_to_n(1)
          → Is 1 <= 0? No
          → Return 1 + sum_to_n(0)

            sum_to_n(0)
              → Is 0 <= 0? Yes! BASE CASE
              → Return 0

          ← 1 + 0 = 1

      ← 2 + 1 = 3

  ← 3 + 3 = 6

Step 5: Verify base cases

Checklist: - [ ] Does the function have at least one base case? - [ ] Does the base case return a value (not recurse)? - [ ] Will the recursive calls eventually reach the base case? - [ ] Does the base case handle all stopping conditions?

Step 6: Apply the fix

Common fixes: - Add missing base case: if condition: return value - Fix base case condition: if n <= 0 instead of if n == 0 - Ensure parameters move toward base case: n - 1 not n + 1

Common Base Case Mistakes

Mistake 1: Base case that's never reached

def countdown_broken(n):
    """BROKEN: Base case checks for n == 0, but we skip it"""
    if n == 0:  # Base case
        return
    print(n)
    countdown_broken(n - 2)  # BUG: Decrements by 2, might skip 0!

# This crashes if n is odd
countdown_broken(5)  # 5 → 3 → 1 → -1 → -3 → ... CRASH

Problem: When n=5, we go 5→3→1→-1, never hitting 0.

Fix: Base case should catch all stopping points:

def countdown_fixed(n):
    """FIXED: Base case handles n <= 0"""
    if n <= 0:  # Catches 0, -1, -2, etc.
        return
    print(n)
    countdown_fixed(n - 2)

countdown_fixed(5)  # Works: 5, 3, 1

Mistake 2: Base case that recurses

def factorial_broken(n):
    """BROKEN: Base case still recurses!"""
    if n == 0:
        return factorial_broken(0)  # BUG: Still recursing!
    return n * factorial_broken(n - 1)

# This crashes immediately
# factorial_broken(5) → ... → factorial_broken(0) → factorial_broken(0) → ...

Problem: Base case calls itself, creating infinite loop at n=0.

Fix: Base case must return a concrete value:

def factorial_fixed(n):
    """FIXED: Base case returns value"""
    if n == 0:
        return 1  # Concrete value, no recursion
    return n * factorial_fixed(n - 1)

Mistake 3: Multiple base cases, missing one

def fibonacci_broken(n):
    """BROKEN: Missing base case for n=1"""
    if n == 0:
        return 0
    # Missing: if n == 1: return 1
    return fibonacci_broken(n - 1) + fibonacci_broken(n - 2)

# This crashes for n=1
# fibonacci_broken(1) → fibonacci_broken(0) + fibonacci_broken(-1)
# fibonacci_broken(-1) → fibonacci_broken(-2) + fibonacci_broken(-3) → ...

Problem: Fibonacci needs TWO base cases (n=0 and n=1). Missing n=1 causes negative recursion.

Fix: Include all necessary base cases:

def fibonacci_fixed(n):
    """FIXED: Both base cases present"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_fixed(n - 1) + fibonacci_fixed(n - 2)

Mistake 4: Parameters don't move toward base case

def sum_list_broken(lst):
    """BROKEN: List never gets smaller!"""
    if len(lst) == 0:
        return 0
    return lst[0] + sum_list_broken(lst)  # BUG: Passing same list!

# This crashes immediately
# sum_list_broken([1,2,3]) → sum_list_broken([1,2,3]) → ...

Problem: Recursive call uses same list, never approaching empty list base case.

Fix: Make problem smaller in recursive call:

def sum_list_fixed(lst):
    """FIXED: List gets smaller each time"""
    if len(lst) == 0:
        return 0
    return lst[0] + sum_list_fixed(lst[1:])  # Remove first element

The Base Case Checklist

Before running any recursive function, verify:

Existence: Does the function have at least one base case? python if base_condition: return base_value
Reachability: Will the recursive calls eventually reach the base case?
Parameters must move toward base case (n decreases, list gets shorter, etc.)
No infinite loops in parameter transformation
Completeness: Does the base case handle all stopping conditions?
Use <= or >= instead of == when appropriate
Multiple base cases if problem has multiple stopping points
Correctness: Does the base case return the right value?
0! = 1 (not 0)
Empty list sum = 0
x^0 = 1
Non-recursion: Does the base case return without recursing?
Must return concrete value
No recursive calls in base case

If any check fails, you'll get infinite recursion.

Practical Exercise: Fix These Broken Functions

Here are 5 broken recursive functions. Each has a base case problem. Identify and fix each one:

# Exercise 1: What's wrong?
def count_up(n, target):
    """Count from n up to target"""
    if n == target:
        return
    print(n)
    count_up(n + 1, target)

# Test: count_up(1, 5) should print 1, 2, 3, 4
# Does it work? Try it!

# Exercise 2: What's wrong?
def find_max(lst):
    """Find maximum value in list"""
    if len(lst) == 1:
        return lst[0]
    return max(lst[0], find_max(lst))

# Test: find_max([3, 1, 4, 1, 5]) should return 5
# Does it work? Try it!

# Exercise 3: What's wrong?
def reverse_string(s):
    """Reverse a string"""
    if len(s) == 0:
        return ""
    return reverse_string(s[1:]) + s[0]

# Test: reverse_string("hello") should return "olleh"
# Does it work? Try it!

# Exercise 4: What's wrong?
def gcd(a, b):
    """Greatest common divisor using Euclidean algorithm"""
    if b == 0:
        return a
    return gcd(b, a % b)

# Test: gcd(48, 18) should return 6
# Does it work? Try it!

# Exercise 5: What's wrong?
def is_palindrome(s):
    """Check if string is palindrome"""
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s)

# Test: is_palindrome("racecar") should return True
# Does it work? Try it!

Solutions:

Exercise 1: Works correctly! This is a trick question—the function is fine.

Exercise 2: Bug: find_max(lst) should be find_max(lst[1:]) (list never gets smaller)

Exercise 3: Works correctly! Another trick—this function is fine.

Exercise 4: Works correctly! GCD is a classic recursive algorithm that's already correct.

Exercise 5: Bug: is_palindrome(s) should be is_palindrome(s[1:-1]) (string never gets smaller)

Key lesson: Not all recursion errors are base case problems. Sometimes the recursive call doesn't make the problem smaller (Exercise 2, 5).

The Journey: From Problem to Solution

Iteration	Failure Mode	Technique Applied	Result	Key Lesson
0	Infinite recursion (countdown)	None	Crashes at depth 1000	Need base case
1	Added base case	`if n < 1: return`	Works correctly	Base case stops recursion
2	Infinite recursion (factorial)	None	Crashes at depth 1000	Same problem, different function
3	Added base case	`if n == 0: return 1`	Works correctly	Base case + return value
4	Negative inputs crash	Input validation	Fails fast with clear error	Validate before recursing
5	Base case never reached	Broader condition	Catches all stopping points	Use `<=` not `==`
6	Base case still recurses	Return concrete value	Stops infinite loop	Base case must not recurse

Final wisdom: The base case is not optional. It's the foundation that makes recursion work. Without it, you have infinite loops. With it, you have elegant solutions.

Lessons Learned

Every recursive function needs a base case that stops the recursion
Base cases must return concrete values, not recurse further
Parameters must move toward the base case with each recursive call
Use <= or >= in base cases when appropriate to catch edge cases
Validate inputs before recursing to fail fast with clear errors
Debug with print statements to visualize the call stack
Trace by hand with small inputs to understand execution flow
Check the base case first when debugging infinite recursion

The recursive mindset: Trust that if you handle the base case correctly and make the problem smaller in each recursive call, the recursion will work. Don't try to trace the entire execution in your head—focus on: - What's the simplest case? (base case) - How do I make the problem smaller? (recursive case) - Will smaller problems eventually reach the base case? (termination)

If you can answer these three questions, your recursive function will work.

Chapter 02: Your First Recursive Functions

Countdown: The Simplest Recursion

Countdown: The Simplest Recursion

Iteration 0: The Broken Version

Diagnostic Analysis: Understanding the Failure

Iteration 1: Adding the Base Case

Manual Trace: Following the Execution

Common Failure Modes and Their Signatures

Symptom: Function prints forever and crashes with RecursionError

Symptom: Function returns immediately without printing anything

Symptom: Function prints one number then stops

Complexity Analysis

Factorial: The Classic Example

Factorial: The Classic Example

Iteration 0: The Broken Version

Diagnostic Analysis: Understanding the Failure

Iteration 1: Adding the Base Case

Manual Trace: Following the Return Values

Iteration 2: Handling Edge Cases

Common Failure Modes and Their Signatures

Symptom: RecursionError with negative numbers in traceback

Symptom: Wrong result (e.g., factorial(5) returns 24 instead of 120)

Symptom: Function works but is very slow for large n

Complexity Analysis

Power Function: Building Intuition

Power Function: Building Intuition

Iteration 0: The Naive Recursive Approach

Iteration 1: The Divide-and-Conquer Insight

Comparing the Two Approaches

Iteration 2: Handling Negative Exponents

Common Failure Modes and Their Signatures

Symptom: Wrong result for even exponents (e.g., 2^4 = 8 instead of 16)

Symptom: RecursionError for negative exponents

Symptom: Slow performance for large n despite using "fast" algorithm

When to Apply Each Solution

Naive Approach: power_naive(x, n)

Fast Approach: power_fast(x, n)

Decision Framework

Complexity Analysis Summary

Naive Approach

Fast Approach (Divide-and-Conquer)

Common Pitfall: Missing Base Cases and Infinite Recursion

Common Pitfall: Missing Base Cases and Infinite Recursion

The Anatomy of Infinite Recursion

Debugging Workflow: When Your Recursive Function Fails

Common Base Case Mistakes

Mistake 1: Base case that's never reached

Mistake 2: Base case that recurses

Mistake 3: Multiple base cases, missing one

Mistake 4: Parameters don't move toward base case

The Base Case Checklist

Practical Exercise: Fix These Broken Functions

The Journey: From Problem to Solution

Lessons Learned

Symptom: Function prints forever and crashes with `RecursionError`

Symptom: `RecursionError` with negative numbers in traceback

Symptom: `RecursionError` for negative exponents

Naive Approach: `power_naive(x, n)`

Fast Approach: `power_fast(x, n)`